package com.easy;

/**
 * Created by Lxk on 2020/2/9.
 */
public class Solution198 {

    /**
     * dp解法：
     * 令f(k)为前k个元素集合的最大偷盗价值,
     * k=1时，价值为f(1)=nums[1]
     * k=2时，价值为f(2)=Max(nums[1],nums[2])
     * k=3时，价值为f(3)=Max(f(1)+nums[3],f(2))
     * ...
     * k=n时，价值为f(n)=Max(f(n-2)+nums[n],f(n-1))
     * 即选择第n个元素的最大值时有两种情况：
     * 1、选取第n个元素，此时n-1个元素不可取，得到f(n-2)+nums[n]
     * 2、不选取第n个元素，此时对应于f(n-1)
     * 在上述两种情况中选取较大的即可
     *
     * @param nums
     * @return
     */
    public int rob(int[] nums) {
        int prePreMax = 0;
        int preMax = 0;
        for (int i = 0; i < nums.length; i++) {
            int curMax = Math.max(prePreMax + nums[i], preMax);
            prePreMax = preMax;
            preMax = curMax;
        }
        return preMax;
    }

    public static void main(String[] args) {
        Solution198 solution198 = new Solution198();
        int[] arr = {2, 7, 9, 3, 1};
        System.out.println(solution198.rob(arr));
    }

}
